Over recent time, geographic, mapping, and navigation information have become widely available to a typical computing device user. Indeed, geographic, mapping, and navigation information is available to personal computers as well as other types of computer devices, such as personal digital assistants (PDAs), hybrid wireless phone/PDAs, on-board navigation devices, and the like. Clearly, some computing devices, especially personal computers, laptops, and the like, are able to locally store, or read computer-readable media having substantial amounts of information. On the other hand, many computing devices, such as handheld computing devices (that include PDAs and hybrid devices), on-board navigation systems, and the like generally do not have large storage capacity, at least for substantial amounts of geographic, mapping, and navigation information.
As an example, FIG. 1 is a pictorial diagram illustrating an exemplary hand-held computing device 100 that could be used to display geographic, mapping, or navigation information to a user. As those skilled in the art will appreciate, such a computing device 100 is usually very limited in the amount of storage available for geographic information. Similarly, FIG. 2 is a pictorial diagram illustrating an exemplary on-board navigation device 200. In order to enable such computing devices to provide geographic, mapping and navigation information (generally referred to as geographic data) to a user, only small portions of the total available geographic information is downloaded to them. Indeed, it is by segmenting geographic information that geographic information providers typically can manage the distribution of information to computing devices, especially to computing devices with limited storage capabilities.
As those skilled in the art will appreciate, geographic information is made available to computing devices in sections, each section corresponding to a particular geographic region. As an example, FIG. 3 illustrates an exemplary region 300 divided into sections, where each section (bounded by dashed lines) corresponds to a block of geographic information that is available for downloading and use by a computing device, such as computing devices 100 and 200. Typically, each section includes all geographic locations and names, as well as routing information corresponding to the physical area within the defined section. For example, assuming the exemplary region 300 corresponds to the Seattle metropolitan area, specific geographic information regarding the downtown area of Seattle would be found in a section corresponding to grid 302.
As should be appreciated, individual sections may include thousands of named items including parks, streets, neighborhoods, landmarks, geographic features, city names, and the like. For example, the second corresponding to grid 302 would include numerous street names, landmarks, parks, and the like as found in the downtown Seattle area. Alternatively, other sections may have very limited information, such as the section corresponding to grid 304 which covers an area of water in the Puget Sound.
Typically, each section of geographic information downloaded to a computing device includes an identifiable list of geographic names corresponding to the various named items in the section. However, unless a named item falls across two sections, an adjacent section typically will not have information regarding named items located in another section. For example, the geographic name list for the section corresponding to grid 302 will likely not include “Alki Point”, which is located in grid 306.
Unfortunately, due to the segmented/sectioned organization of geographic information, a computing device had to search successively through numerous sections of geographic information until a sought-for named geographic item was found, or store a single, large list of geographic names for the entire region 300, which is not storage efficient. Clearly, sequentially searching through multiple sections of geographic information to find a named item is, at very best, extremely inefficient. Furthermore, as many computing devices have limited storage capacity, they may not be able to store holding multiple sections of geographic information. In such circumstances, the computing device must swap one section for another, which is also very inefficient because frequently used data may be swapped out (for later retrieval), and because obtaining another section may involve substantial use of limited resources. While it may be necessary on occasions to swap sections, doing so to locate geographically named items in a sequential search of the sections is not ideal.
In light of the current inefficiencies in locating geographically named items among sections of geographic information, what is needed is an efficient system for locating such geographically named items. The present invention addresses this and other items found in the prior art.